/*编写一个高效的算法来判断 m*n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
* 每行中的整数从左到右按升序排列。
* 每行的第一个整数大于前一行的最后一个整数。
*
* 输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
* 输出：true
* */

package newcoder.BinarySearch_4;

public class Leetcode74 {

    public static void main(String[] args) {

        Leetcode74 obj = new Leetcode74();
        int[][] matrix = {{1,3,5,7}, {10,11,16,20}, {23,30,34,60}};
        int target = 13;
        System.out.println(obj.searchMatrix(matrix, target));
    }

    public boolean searchMatrix(int[][] matrix, int target){

        int m = matrix.length, n = matrix[0].length;
        if (m == 0 || n == 0){
            return false;
        }
        int left = 0, right = m * n - 1;
        while (left <= right){

            int pivot = (left + right) / 2;
            if (matrix[pivot / n][pivot % n] == target){
                return true;
            }
            if (matrix[pivot / n][pivot % n] < target){
                left = pivot + 1;
            }else {
                right = pivot - 1;
            }
        }
        return false;
    }
}
